package Demo2;

public class CircularLinkedList {
//    使用循环链表解决 约瑟夫环问题 !
    static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public Node createCircular(int n) {
        if (n <= 0) {
            return null;
        }

        Node head = new Node(1);  // 第一个节点
        Node prev = head;         // 用于构建链表的指针

        // 创建环形链表
        for (int i = 2; i <= n; i++) {
            Node newNode = new Node(i);
            prev.next = newNode;
            prev = newNode;
        }

        prev.next = head;  // 形成循环链表，最后一个节点指向第一个节点
        return head;       // 返回头节点
    }

    // 解决约瑟夫环问题
    public int solveJosephus(Node head, int k) {
        if (head == null || head.next == head){
            return head != null ? head.value : -1;
        }

        Node prev = head;
        Node cur = head;

        // 找到最后一个节点（prev 最终指向最后一个节点）
        while (prev.next != head) {
            prev = prev.next;
        }

        while(cur != cur.next){
            for (int i = 1; i < k; i++) {
                prev = cur;
                cur = cur.next;
            }
//            删除该节点
            System.out.println("删除节点: " + cur.value);
            prev.next = cur.next;
            cur = cur.next;
        }
        return cur.value;
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();

        // 1. 创建循环链表
        int n = 6; // 总人数
        Node head = list.createCircular(n);

        // 2. 设置每数到第几个人就出列
        int k = 3;

        // 3. 解决约瑟夫环问题，输出最后的幸存者
        int survivor = list.solveJosephus(head, k);
        System.out.println("最后的幸存者是: " + survivor);

    }

}
